package com.sakura.二分查找;

import java.lang.reflect.Array;
import java.util.Arrays;

// 给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
//
//「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
public class Code02_两个数组间的距离值 {


    public static void main(String[] args) {
        int[] arr1 = {-3,10,2,8,0,10};
        int[] arr2 = {-9,-1,-4,-9,-8};
        System.out.println(findTheDistanceValue(arr1, arr2, 9));
    }

    // 对于 arr1 中的元素 x，如果 arr2 没有在 [x−d,x+d] 中的数，那么答案加一。
    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int x : arr1) {
            int i = Arrays.binarySearch(arr2, x - d);
            if (i < 0) {
                // 如果 i < 0，表示在 arr2 中没有找到 x - d。
                //此时，~i 操作将负数转换为插入点的索引。~i 等价于 -i - 1，表示如果要将 x - d 插入到数组中的位置。
                // 通过这个操作，可以确定 x - d 应该插入的位置，从而用于后续判断 arr2 中是否存在位于 [x-d, x+d] 区间内的元素
                i = ~i; // -i - 1
            }
            if (i == arr2.length || arr2[i] > x + d) {
                ans++;
            }

        }
        return ans;
    }


}
